package zuoshen_video2.structure;
/* 
    跳表类
*/


public class SKList {
    
    class SKNode {
        int key;
        int val;
        int level;
        SKNode[] nexts;

        public SKNode() {

        }

        public SKNode(int key, int val) {
            this.key = key;
            this.val = val;
        }

         public SKNode(int key, int val, int level) {
            this.key = key;
            this.val = val;
            this.level = level;
            this.nexts = new SKNode[level + 1];
        }
    }

    int maxLevel;
    SKNode head;

    public SKList(int maxLevel) {
        //直接初始化一个最大高度
        head = new SKNode(0, 0, maxLevel);
        this.maxLevel = maxLevel;
    }

    /* 
        随机设定一个新节点的链表长度
     */
    public int randomLevel() {
        return (int)(Math.random() * maxLevel);
    }

    /* 
        查找对应层上一个比key小的节点中key最大的那个(不是key对应的节点)
    */
    public SKNode preMax(int key, int level) {
        SKNode cur = head, next;
        while ((next = cur.nexts[level]) != null
         && next.key < key) {
            cur = next;
        }
        return cur;
    }

    /* 
        查找对应的key的SKNod
    */
    public SKNode find(int key) {
        int l = maxLevel;
        SKNode pre = head;
        while (l >= 0) {
            pre = preMax(key, l);
            if (pre != null && pre.nexts[l] != null && pre.nexts[l].key != key)
                 return pre.nexts[l];
            l--;
         }
         return null;
    }

    /* 
        添加一个kv对构成的SKNode
    */
    public void insert(int key, int val) {
        int l = randomLevel();
        SKNode pre = null;
        SKNode node = new SKNode(key, val, l);
        while (l >= 0) {
            pre = preMax(key, l);
            node.nexts[l] = pre.nexts[l];
            pre.nexts[l] = node;
            l--;
        }
    }

    /* 
        删除key对应的节点
    */
    public void remove(int key) {
        SKNode node = find(key), pre;
        if (node == null) return;
        int l = node.level;
        while (l >= 0) {
            pre = preMax(key, l);
            pre.nexts[l] = node.nexts[l];
            l--;
        }
    }


}
